package cn.guo.algorithm.sort.exchange;

import cn.guo.algorithm.AlgorithmUtils;

import java.util.List;

/**
 * TODO: 冒泡排序 冒泡的时间复杂度为： 0(n) - 0(n^2)
 * [50,10,30,20,40]
 * 要达到冒泡的效果，我们就要把一组数字竖起来看，大家想想，如何冒泡？如何来体会重的沉底，轻的上浮？
 * <p/>
 * 第一步:  我们拿40跟20比，发现40是老大，不用交换。
 * 第二步:  然后向前推一步，就是拿20跟30比，发现30是老大，就要交换了。
 * 第三步：拿交换后的20跟10比，发现自己是老大，不用交换。
 * 第四步：拿10跟50交换，发现50是老大，进行交换。
 * <p/>
 * 最后，我们经过一次遍历，把数组中最小的数字送上去了，看看，我们向目标又迈进了一步。
 * <p/>
 * Created by guo on 2015/10/19.
 */
public class BubbleSort {

    public static void main(String[] args) {
        //产生随机数组
        int length = 1000;
        long a = System.currentTimeMillis();
        List<Integer> arr = AlgorithmUtils.getRandomList2(length);
        long b = System.currentTimeMillis();
        AlgorithmUtils.asyncPrintMsg("生成[" + length + "]个不等随机数耗时[" + (b - a) + "]ms");
        AlgorithmUtils.asyncPrintArrayList(arr);
        //对随机数进行
        arr = getBubbleSoredList(arr);
        long c = System.currentTimeMillis();
        AlgorithmUtils.asyncPrintMsg("冒泡排序大小为[" + length + "]的数组,耗时[" + (c - b) + "]ms");
        AlgorithmUtils.asyncPrintArrayList(arr);
    }

    private static List<Integer> getBubbleSoredList(List<Integer> arr) {
        int temp;
        for(int i=0;i<arr.size()-1;i++){
            for(int j=arr.size()-1;j>i;j--){
                if(arr.get(j-1) > arr.get(j)){
                    temp = arr.get(j-1);
                    arr.set(j-1,arr.get(j));
                    arr.set(j,temp);
                }
            }
        }
        return arr;
    }

}
